class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> index(n);
        for (int i = 0; i < n; i++) index[i] = i;

        sort(nums1.begin(), nums1.end());
        sort(index.begin(), index.end(), [&](int i, int j) {
            return nums2[i] < nums2[j];
            });

        vector<int> ret(n);
        int left = 0, right = n - 1;
        for (int i = 0; i < n; i++)
        {
            if (nums1[i] > nums2[index[left]])
            {
                ret[index[left]] = nums1[i];
                left++;
            }
            else
            {
                ret[index[right]] = nums1[i];
                right--;
            }
        }

        return ret;
    }
};